//
// Created by yangchao on 2022/5/10.
// 62. 不同路径: https://leetcode.cn/problems/unique-paths/
//

#include <iostream>
#include <vector>
using namespace std;

class UniquePaths{
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> dp(m,vector<int>(n));
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (i == 0 || j == 0) {
                    dp[i][j] = 1;
                } else {
                    dp[i][j] = dp[i-1][j] + dp[i][j-1];
                }
            }
        }
        return dp[m-1][n-1];
    }
};

int main() {
    UniquePaths uq;
    int res = uq.uniquePaths(3,7);
    cout << res << endl;
}


